package com.bascker.algorithm.practice.heap.minheap.ksmallestpairs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * TTL 解法： 暴力枚举每对选项，将其放入最小堆中，弹出 k 次堆顶元素进行存储即为结果
 */
public class Solution1 {

    // 1 <=  nums1.length, nums2.length
    // 1 <= k <= nums1.length * nums2.length
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;

        // 声明最小堆：根据和进行降序排序
        PriorityQueue<Data> minHeap = new PriorityQueue<>(new Comparator<Data>() {
            @Override
            public int compare(Data o1, Data o2) {
                return o1.sum - o2.sum;
            }
        });

        // 哈希表去重：防止重复压入元素
        Set<Data> set = new HashSet<>();

        // 暴力枚举所有选项，加入堆中
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                Data data = new Data(nums1[i], nums2[j]);
                if (set.contains(data)) {
                    continue;
                }

                minHeap.offer(data);
                set.add(data);
            }
        }

        // 弹出堆顶元素
        List<List<Integer>> rs = new ArrayList<>();
        for (int i = 0; i < k; i ++) {
            Data data = minHeap.poll();
            rs.add(Arrays.asList(data.v1, data.v2));
        }

        return rs;
    }

    static class Data {
        int v1;

        int v2;

        int sum;

        public Data(int v1, int v2) {
            this.v1 = v1;
            this.v2 = v2;
            sum = v1 + v2;
        }
    }

}
